/*
【例6.3】
有10个地区的面积，要求对它们按由小到大的顺序排列

解题思路：每次将相邻两个数比较
2,3,1,6,4,5,7,9,8,0


选择排序：
缺点：时间复杂度O(n^2)太高，效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。
优点：一轮比较只需要换一次位置；

冒泡排序：
缺点:时间复杂度O(n^2)太高，效率慢；
优点:比较简单，空间复杂度（最优O(0),最坏O(n),平均O(1)）较低，是稳定的（不会改变相同数字的顺序）；


插入排序：
【算法分析】
（1）时间复杂度
直接插入排序的时间复杂度为O（n^2）
（2）空间复杂度
直接插入排序只需一个记录的辅助空间r[0]，所以空间复杂度为O(1)。
【算法特点】
（1）稳定排序。
（2）算法简便，容易实现
（3）也适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针。
（4）更适用于基本有序的情况，当初始记录无序，n较大时，此算法复杂度较高，不宜采用。
*/

#include<stdio.h>
int main()
{
    
    int a[10] = {2,3,1,6,4,5,7,9,8,0};
    int i;

    // void select_sort(int b[]);  //声明，将在main函数中调用这个函数
    // select_sort(a);
    // void maopao_sort(int b[]);
    // maopao_sort(a);
   void InsertSort(int b[],int len);
   InsertSort(a,10);

    printf("the sorted numbers :\n");
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}


void select_sort(int b[])   // void 空，无需return
{
     /*
    选择排序          {2,      3,      1,      6,      4,      5,      7,      9,      8,      0}       
                    a[i]                                                                      a[k] 
                                                                                             a[pos]
    i=0循环结束后     {0,      3,      1,      6,      4,      5,      7,      9,      8,      2}     比较（循环）了9次
    i=1循环结束后     {0,      1,      3,      6,      4,      5,      7,      9,      8,      2}     比较了8次
    ...
    i=9循环结束后     {0,      1,      2,      3,      4,      5,      6,      7,      8,      9}     比较了1次
    */
    int pos,i,k,t;
    for(i=0;i<10;i++)  //遍历
    {
        pos=i;  //pos用于记录最小数的下标
        for(k=i+1;k<10;k++)   //遍历
        {
            if(b[k]<b[pos])
            {
                pos=k;
            }
        }
        if(pos!=i)
        {
            t=b[i];     //用t作为临时变量交换a[i],a[pos]
            b[i]=b[pos];
            b[pos]=t;
        }
    }
}

void maopao_sort(int b[])
{
    /*
    冒泡排序法          10个数需进行9趟（轮）两两比较。每一趟，最大的数都会排到最后
    原数列：    {2,      3,      1,      6,      4,      5,      7,      9,      8,      0}           j
    j=0 趟之后  {2,      1,      3,      4,      5,      6,      7,      8,      0,      9}  比较i=9- 0 = 9次
    j=1 趟之后  {1,      2,      3,      4,      5,      6,      7,      0,      8,      9}  比较i=9- 1 = 8次
    ....
    j=8 趟之后  {0,      1,      2,      3,      4,      5,      6,      7,      8,      9}  比较i=9- 8 = 1次,共比较了45次
    */
    int i,j,t;
    for(j=0;j<9;j++)               //j记录的是趟数，进行9次循环，实现9趟比较
    {
        for(i=0;i<9-j;i++)         //在每一趟中进行9-j次比较
        {
            if(b[i]>b[i+1])         //相邻两个数进行比较
            { 
                t = b[i];                 //   y = x + 1 
                b[i] = b[i+1];
                b[i+1] = t;
            }
        }
    }
}


void InsertSort(int b[],int len)
{
    
	int i,j;
	//第一个for循环 遍历无序序列 
	for(i=1;i<len;i++)
    {  //从数组的第二个元素开始依次遍历无序序列 
	 	int temp = b[i];  //临时保存将要排序的元素 
	 	//第二个for循环遍历有序序列 
	 	for(j=i-1;  temp<b[j]&&j>=0  ;j--)      //条件不满足时，结束循环
        {  //将待排序元素依次和有序序列中的元素比较 
	 		b[j+1] = b[j];	 		//待排序元素 小于 有序序列中当前元素时 将该元素后移
	 	}
    // printf("i=%d循环结束后j=%d\n",i,j);
	b[j+1] = temp;  //待排序元素 大于 有序序列最后一个元素 直接将该元素插入到有序序列最后 
	}
}
/*
    插入排序        {2,      3,      1,      6,      4,      5,      7,      9,      8,      0} 
    i = 1                   b[i]
                            temp
            j=0     b[j]    b[j+1]
                    {2,      3,      1,      6,      4,      5,      7,      9,      8,      0} 
    i = 2                           b[i]
                                    temp
            j=1             b[j]    b[j+1]
                    {2,      3,      3,      6,      4,      5,      7,      9,      8,      0}                     
            j=0     b[j]    b[j+1]
                    {2,      2,      3,      6,      4,      5,      7,      9,      8,      0}
            j=-1,不满足循环条件,结束循环,执行b[j+1] = temp;
            b[j]    b[j+1]
                    {1,      2,      3,      6,      4,      5,      7,      9,      8,      0}

    i = 2             {1,      2,      3,      6,      4,      5,      7,      9,      8,      0}  
    i = 3             {1,      2,      3,      6,      4,      5,      7,      9,      8,      0}  
                      {1,      2,      3,      6,      4,      5,      7,      9,      8,      0}  
    i = 4                                             b[i]
                                                      temp
            j=3                               b[j]    b[j+1]
                      {1,      2,      3,      6,      6,      5,      7,      9,      8,      0} 
            j=2,不满足循环条件,结束循环,执行b[j+1] = temp;
                                    b[j]    b[j+1]
                      {1,      2,      3,      4,      6,      5,      7,      9,      8,      0} 

*/